package com.跳台阶问题;

import java.util.ArrayList;
import java.util.List;

public class Solution1 {
	List<List<Integer>> result = new ArrayList<List<Integer>>();

	public List<List<Integer>> combinationSum(int[] candidates, int target) {

		List<Integer> list = new ArrayList<Integer>();
		backtracking(candidates, target, 0, list);// 给定target，start=0表示从数组第一个开始
		return result;// 返回解的组合链表
	}

	public void backtracking(int[] candidates, int target, int start, List<Integer> list) {

		if (target < 0)
			return;// 凑过头了
		else if (target == 0) {

			result.add(new ArrayList<>(list));// 正好凑出答案，开心地加入解的链表
            System.out.println(result);
		} else {
			for (int i = start; i < candidates.length; i++) {// 循环试探每个数
				list.add(candidates[i]);// 尝试加入
				// 下一次凑target-candidates[i]，允许重复，还是从i开始
				backtracking(candidates, target - candidates[i], i, list);
				list.remove(list.size() - 1);// 回退
			}
		}

	}
}
